package com.daaij.firstchapter;

import com.daaij.seventhchapter.MultiThreadSort;

import java.util.*;

/**
 * 选择问题，给定n个数，找出第k个大的数。
 */
public class SelectionProblem {

    //思路一，排序后再找到第k个
    public static int select(int[] input,int k){
        sort(input);
        return input[k];
    }

    //思路二，排序k个数，对k之后的数进行遍历：如果被遍历到的数小于前面k个的最小数，则忽略，否则，更新前k个数。
    public static int select1(int[] input,int k){
        sortPart(input,k); //这里可以少排一点序，但是这个优化对于本身就会对所有数排序的方法（树），和不进行排序的方法（堆）无效。
        foreachRestAndUpdate(input,k);
        return input[k];
    }

    private static void foreachRestAndUpdate(int[] input, int k) {

    }

    private static void sortPart(int[] input, int k) {


    }

    private static void sort(int[] input){

    }

    //快速选择,选出input中第k个大的数，从大到小,平均时间复杂度为n
    private static int quickSelect(int[] input,int k){
        return quickSelectInner(0,input.length - 1,input,k - 1);
    }

    private static int quickSelectInner(int start, int end, int[] input, int k) {

        if(end >= start){
            if(k == start && k == end){
                return input[start];
            }
        }

        int standard = selectStandardAndSwap(start,end,input);

        int ascIndex = start;
        int descIndex = end - 1;

        while(ascIndex <= descIndex){

            while(ascIndex < end && input[ascIndex ++] > standard){
            }

            while(descIndex >= start && input[descIndex --] < standard){
            }

            if(ascIndex - 1 < descIndex + 1 && ascIndex - 1 >= 0) {
                swap(input, ascIndex - 1, descIndex + 1);
            }
        }

        swap(input,ascIndex - 1,end);

        if(k == ascIndex - 1){
            return input[ascIndex - 1];
        }else if(k < ascIndex - 1){
            return quickSelectInner(start,ascIndex - 2,input,k);
        }else{
            return quickSelectInner(ascIndex,end,input,k);
        }

    }

    private static int selectStandardAndSwap(int start, int end, int[] input) {

        int middle = (start + end) / 2;
        int startValue = input[start];
        int endValue = input[end];
        int middleValue = input[middle];

        if(startValue >= middleValue){
            if(middleValue >= endValue){
                swap(input,middle,end);
            }else if(startValue <= endValue){
                swap(input,start,end);
            }
        }else{
            if(startValue >= endValue){
                swap(input,start,end);
            }else if(middleValue <= endValue){
                swap(input,middle,end);
            }
        }
        return input[end];
    }

    private static void swap(int[] input,int first,int second){
        int tmp = input[first];
        input[first] = input[second];
        input[second] = tmp;
    }

    //第十章，选择问题最坏情况下依然线性时间的算法 TODO

    //

    //选择问题下界

    public static void main(String[] args){

        int count = 10000;
        int range = 50000;
        int k = 5668;
        int sortTimes = 1;

        Random random = new Random();
        int[] array = new int[count];

        for(int i = 0; i < count; i ++) {
            array[i] = random.nextInt(range);
        }


        long before = System.currentTimeMillis();
        System.out.println(before);
        while(sortTimes -- > 0){
            System.out.println(quickSelect(array,k));
        }
        long after = System.currentTimeMillis();


        System.out.println(Arrays.toString(array));
        System.out.println(after - before);

    }

}
